{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Car Fleet II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #math #monotonic-stack #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #数学 #单调栈 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getCollisionTimes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #车队 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一条单车道上有 <code>n</code> 辆车，它们朝着同样的方向行驶。给你一个长度为 <code>n</code> 的数组 <code>cars</code> ，其中 <code>cars[i] = [position<sub>i</sub>, speed<sub>i</sub>]</code> ，它表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>position<sub>i</sub></code> 是第 <code>i</code> 辆车和道路起点之间的距离（单位：米）。题目保证 <code>position<sub>i</sub> < position<sub>i+1</sub></code><sub> </sub>。</li>\n",
    "\t<li><code>speed<sub>i</sub></code> 是第 <code>i</code> 辆车的初始速度（单位：米/秒）。</li>\n",
    "</ul>\n",
    "\n",
    "<p>简单起见，所有车子可以视为在数轴上移动的点。当两辆车占据同一个位置时，我们称它们相遇了。一旦两辆车相遇，它们会合并成一个车队，这个车队里的车有着同样的位置和相同的速度，速度为这个车队里 <strong>最慢</strong> 一辆车的速度。</p>\n",
    "\n",
    "<p>请你返回一个数组 <code>answer</code> ，其中 <code>answer[i]</code> 是第 <code>i</code> 辆车与下一辆车相遇的时间（单位：秒），如果这辆车不会与下一辆车相遇，则 <code>answer[i]</code> 为 <code>-1</code> 。答案精度误差需在 <code>10<sup>-5</sup></code> 以内。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>cars = [[1,2],[2,1],[4,3],[7,2]]\n",
    "<b>输出：</b>[1.00000,-1.00000,3.00000,-1.00000]\n",
    "<b>解释：</b>经过恰好 1 秒以后，第一辆车会与第二辆车相遇，并形成一个 1 m/s 的车队。经过恰好 3 秒以后，第三辆车会与第四辆车相遇，并形成一个 2 m/s 的车队。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>cars = [[3,4],[5,4],[6,3],[9,1]]\n",
    "<b>输出：</b>[2.00000,1.00000,1.50000,-1.00000]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= cars.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= position<sub>i</sub>, speed<sub>i</sub> <= 10<sup>6</sup></code></li>\n",
    "\t<li><code>position<sub>i</sub> < position<sub>i+1</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [car-fleet-ii](https://leetcode.cn/problems/car-fleet-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [car-fleet-ii](https://leetcode.cn/problems/car-fleet-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,1],[4,3],[7,2]]', '[[3,4],[5,4],[6,3],[9,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        stark, res = [], []\n",
    "        while cars:\n",
    "            y, k = cars.pop()\n",
    "            while len(stark) > 1 and stark[-1][0] * k + y <= stark[-1][1]:\n",
    "                stark.pop()\n",
    "            if stark and stark[-1][2] < k:\n",
    "                a, b, c = stark[-1]\n",
    "                X = b-a*c\n",
    "                res.append((X-y)/(k-c))\n",
    "                stark.append([(X-y)/(k-c), (k*X-y*c)/(k-c), k])\n",
    "            else:\n",
    "                res.append(-1.0)\n",
    "                stark = [[0,y,k]]\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        #copy\n",
    "        n = len(cars)\n",
    "        ans = [-1.0] * n\n",
    "        stack  = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            pos,speed  = cars[i]\n",
    "\n",
    "            while stack and speed <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "            \n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                time = (cars[j][0] -pos)/(speed - cars[j][1])\n",
    "                if ans[j] <0 or time <= ans[j]:\n",
    "                    ans[i] = time\n",
    "                    break\n",
    "                stack.pop()\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n=len(cars)\n",
    "        ans=[-1]*n\n",
    "        q=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            c=cars[i]\n",
    "            while len(q)!=0:\n",
    "                p=cars[q[-1]]\n",
    "                if c[1]<=p[1]:q.pop()\n",
    "                else:\n",
    "                    if ans[q[-1]]<0:break\n",
    "                    if (p[0]-c[0])/(c[1]-p[1])<=ans[q[-1]]:break\n",
    "                    q.pop()\n",
    "            if len(q)!=0:\n",
    "                p=cars[q[-1]]\n",
    "                ans[i]=(p[0]-c[0])/(c[1]-p[1])\n",
    "            q.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "\n",
    "        n = len(cars)\n",
    "        ans = [-1.0] * n\n",
    "        stack = [] # 单调栈，栈底：车速更慢，且初始位置更靠右\n",
    "\n",
    "        for i in range(n-1, -1, -1): # 从右往左遍历\n",
    "            pos, speed = cars[i]\n",
    "\n",
    "            # 弹出栈顶速度更快的车辆，直到栈顶车的速度小于当前车辆\n",
    "            while stack and speed <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "\n",
    "            # 从栈顶往栈底依次检查当前车是否能及时追上目标车辆\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                time = (cars[j][0] - pos) / (speed - cars[j][1])\n",
    "                if ans[j] < 0 or time <= ans[j]: # 若及时追上了，此即为解\n",
    "                    ans[i] = time\n",
    "                    break \n",
    "                stack.pop() # 否则弹出栈顶这辆已经检查过的车，准备看下一辆\n",
    "\n",
    "            stack.append(i) # 此时当前车辆的速度一定大于栈顶的车辆，需入栈\n",
    "\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\r\n",
    "        n = len(cars)\r\n",
    "        res = [-1.0] * n\r\n",
    "        st: list[int] = list()\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            while st:\r\n",
    "                if cars[st[-1]][1] < cars[i][1]:\r\n",
    "                    t = (cars[st[-1]][0] - cars[i][0]) / (cars[i][1] - cars[st[-1]][1])\r\n",
    "                    if res[st[-1]] == -1.0 or t <= res[st[-1]]:\r\n",
    "                        res[i] = t\r\n",
    "                        break\r\n",
    "                st.pop()\r\n",
    "            st.append(i)\r\n",
    "\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        stack = []\n",
    "        n = len(cars)\n",
    "        res = [0.0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                if cars[i][1] > cars[j][1]:\n",
    "                    t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])\n",
    "                    if t <= res[j] or res[j] == -1:\n",
    "                        res[i] = t\n",
    "                        break\n",
    "                stack.pop()\n",
    "\n",
    "            if not stack:\n",
    "                res[i] = -1.0\n",
    "            stack.append(i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        l = len(cars)\n",
    "        ret = [-1.0] * len(cars)\n",
    "        stack = []\n",
    "        for i in range(l-1, -1, -1):\n",
    "            b1, v1 = cars[i]\n",
    "            while stack:\n",
    "                b2, v2 = stack[-1]\n",
    "                if v2 >= v1:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    t2 = (b2-b1) / (v1-v2)\n",
    "                    if len(stack) > 1:\n",
    "                        b3, v3 = stack[-2]\n",
    "                        t3 = (b3-b1) / (v1-v3)\n",
    "                        if t2 >= t3:\n",
    "                            stack.pop()\n",
    "                        else:\n",
    "                            ret[i] = t2\n",
    "                            break\n",
    "                    else:\n",
    "                        ret[i] = t2\n",
    "                        break\n",
    "            stack.append((b1, v1))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "\n",
    "        n = len(cars)\n",
    "        res = [-1] * n\n",
    "        stack = [n - 1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            while stack and cars[i][1] <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "            \n",
    "            while stack and (cars[stack[-1]][0] - cars[i][0]) / (cars[i][1] - cars[stack[-1]][1]) > res[stack[-1]] and res[stack[-1]] > 0:\n",
    "                stack.pop()\n",
    "                    \n",
    "            if stack:\n",
    "                res[i] = (cars[stack[-1]][0] - cars[i][0]) / (cars[i][1] - cars[stack[-1]][1])\n",
    "            else:\n",
    "                res[i]\n",
    "            stack.append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n = len(cars)\n",
    "        t, catch = [-1.00000 for _ in range(n)], [n for _ in range(n)]\n",
    "        stack = list()\n",
    "        for i in range(n):\n",
    "            while stack and cars[stack[len(stack)-1]][1] > cars[i][1]:\n",
    "                index = stack.pop()\n",
    "                t[index] = float((cars[i][0]-cars[index][0])/(cars[index][1]-cars[i][1]))\n",
    "                catch[index] = i\n",
    "            stack.append(i)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if t[i] != -1.00000 and t[catch[i]] != -1.00000:\n",
    "                while t[catch[i]] < t[i] and t[catch[i]] != -1:\n",
    "                    t[i] = float((cars[ catch[catch[i]] ][0]-cars[i][0])/(cars[i][1]-cars[catch[catch[i]]][1]))\n",
    "                    catch[i] = catch[catch[i]]\n",
    "        return t\n",
    "\n",
    "# 作者：Cold Code\n",
    "# 链接：https://leetcode.cn/problems/car-fleet-ii/solutions/1706482/by-cold-code-e-15m5/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        stack = []\n",
    "        n = len(cars)\n",
    "        res = [0.0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                if cars[i][1] > cars[j][1]:\n",
    "                    t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])\n",
    "                    if t <= res[j] or res[j] == -1:\n",
    "                        res[i] = t\n",
    "                        break\n",
    "                stack.pop()\n",
    "\n",
    "            if not stack:\n",
    "                res[i] = -1.0\n",
    "            stack.append(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "#         stack = []\n",
    "#         n = len(cars)\n",
    "#         res = [0.0] * n\n",
    "#         for i in range(n - 1, -1, -1):\n",
    "#             while stack:\n",
    "#                 j = stack[-1]\n",
    "#                 if cars[i][1] > cars[j][1]:\n",
    "#                     t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])\n",
    "#                     if t <= res[j] or res[j] == -1:\n",
    "#                         res[i] = t\n",
    "#                         break\n",
    "#                 stack.pop()\n",
    "\n",
    "#             if not stack:\n",
    "#                 res[i] = -1.0\n",
    "#             stack.append(i)\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n = len(cars)\n",
    "        res = [-1 for _ in range(n)]\n",
    "        # 如果后车追上前车，前车速度必小于后车；因此无论后车是否追上前车，前车速度不变\n",
    "        # 此时后车速度必定减小，可以使用一个list记录后车各时间段速度\n",
    "        speedlist = [[0, cars[-1][1]]]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            p, s = cars[i]\n",
    "            if s <= speedlist[0][1]:\n",
    "                speedlist = [[0, s]]\n",
    "            else:\n",
    "                distence = cars[i+1][0] - p\n",
    "                current = 0\n",
    "                while len(speedlist)>1:\n",
    "                    time = speedlist[-2][0]\n",
    "                    speed = speedlist[-1][1]\n",
    "                    if (time-current) * (s-speed) >= distence:\n",
    "                        speedlist[-1][0] = current + distence/(s-speed)\n",
    "                        res[i] = speedlist[-1][0]\n",
    "                        speedlist.append([0, s])\n",
    "                        break\n",
    "                    else:\n",
    "                        distence -= (time-current) * (s-speed)\n",
    "                        current = time\n",
    "                        speedlist.pop()\n",
    "                if len(speedlist) == 1:\n",
    "                    speed = speedlist[0][1]\n",
    "                    time = distence/(s-speed) + current\n",
    "                    res[i] = time\n",
    "                    speedlist[0][0] = time\n",
    "                    speedlist.append([0, s])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n = len(cars)\n",
    "        ans = [-1] * n\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p,s = cars[i] \n",
    "            while st and st[-1][2] >= s: st.pop() # 追不上的车\n",
    "            while st and ans[st[-1][0]] != -1 and st[-1][1] + ans[st[-1][0]]*st[-1][2] > p + ans[st[-1][0]]*s: st.pop() # 还没等遇到就已经被合并的车\n",
    "            if st: ans[i] = (st[-1][1]-p)/(s-st[-1][2])\n",
    "            st.append((i,p,s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        #copy\n",
    "        n = len(cars)\n",
    "        ans = [-1.0] * n\n",
    "        stack  = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            pos,speed  = cars[i]\n",
    "\n",
    "            while stack and speed <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "            \n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                time = (cars[j][0] -pos)/(speed - cars[j][1])\n",
    "                if ans[j] <0 or time <= ans[j]:\n",
    "                    ans[i] = time\n",
    "                    break\n",
    "                stack.pop()\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n=len(cars)\n",
    "\n",
    "        ans=[-1.0]*n\n",
    "        stack=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            pos,speed = cars[i]\n",
    "            while stack and speed <=cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "            while stack:\n",
    "                nex=stack[-1]\n",
    "                t=(cars[nex][0]-pos)/(speed-cars[nex][1])\n",
    "                if ans[nex]==-1.0 or t< ans[nex]:\n",
    "                    ans[i]=t\n",
    "                    break\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n = len(cars)\n",
    "        ans = [-1] * n\n",
    "        st = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            p, s = cars[i]\n",
    "            while st and st[-1][1] >= s:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                while len(st) > 1 and (st[-1][0] - p) / (s - st[-1][1]) >= st[-1][2]:\n",
    "                    st.pop()\n",
    "                t = (st[-1][0] - p) / (s - st[-1][1])\n",
    "                st.append((p, s, t))\n",
    "                ans[i] = t\n",
    "            else:\n",
    "                st.append((p, s, -1))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "\n",
    "        n = len(cars)\n",
    "        ans = [-1.0] * n\n",
    "        stack = [] # 单调栈，栈底：车速更慢，且初始位置更靠右\n",
    "\n",
    "        for i in range(n-1, -1, -1): # 从右往左遍历\n",
    "            pos, speed = cars[i]\n",
    "\n",
    "            # 弹出栈顶速度更快的车辆，直到栈顶车的速度小于当前车辆\n",
    "            while stack and speed <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "\n",
    "            # 从栈顶往栈底依次检查当前车是否能及时追上目标车辆\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                time = (cars[j][0] - pos) / (speed - cars[j][1])\n",
    "                if ans[j] < 0 or time <= ans[j]: # 若及时追上了，此即为解\n",
    "                    ans[i] = time\n",
    "                    break \n",
    "                stack.pop() # 否则弹出栈顶这辆已经检查过的车，准备看下一辆\n",
    "\n",
    "            stack.append(i) # 此时当前车辆的速度一定大于栈顶的车辆，需入栈\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "\n",
    "        n = len(cars)\n",
    "        ans = [-1.0] * n\n",
    "        stack = [] # 单调栈，栈底：车速更慢，且初始位置更靠右\n",
    "\n",
    "        for i in range(n-1, -1, -1): # 从右往左遍历\n",
    "            pos, speed = cars[i]\n",
    "\n",
    "            # 弹出栈顶速度更快的车辆，直到栈顶车的速度小于当前车辆\n",
    "            while stack and speed <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "\n",
    "            # 从栈顶往栈底依次检查当前车是否能及时追上目标车辆\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                time = (cars[j][0] - pos) / (speed - cars[j][1])\n",
    "                if ans[j] < 0 or time <= ans[j]: # 若及时追上了，此即为解\n",
    "                    ans[i] = time\n",
    "                    break \n",
    "                stack.pop() # 否则弹出栈顶这辆已经检查过的车，准备看下一辆\n",
    "\n",
    "            stack.append(i) # 此时当前车辆的速度一定大于栈顶的车辆，需入栈\n",
    "\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, c: List[List[int]]) -> List[float]:\n",
    "        s = []\n",
    "        n = len(c)\n",
    "        ans = [-1]*n\n",
    "        for j in range(n)[::-1]:\n",
    "            while s and c[s[-1]][1]>=c[j][1]:\n",
    "                s.pop()\n",
    "            while s:\n",
    "                p1, v1 = c[s[-1]]\n",
    "                t = (p1 - c[j][0])/(c[j][1] - v1)\n",
    "                if ans[s[-1]]==(-1) or t<=ans[s[-1]]:\n",
    "                    ans[j] = t \n",
    "                    break \n",
    "                s.pop()\n",
    "            s.append(j)\n",
    "        return ans \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Stack():\n",
    "    def __init__(self):\n",
    "        self.num_list = [0] * 210000\n",
    "        self.index = 0\n",
    "\n",
    "    def empty(self):\n",
    "        if self.index == 0:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def push(self, ele):\n",
    "        self.num_list[self.index] = ele\n",
    "        self.index = self.index + 1\n",
    "\n",
    "\n",
    "    def pop(self):\n",
    "        self.index = self.index - 1\n",
    "        return self.num_list[self.index]\n",
    "\n",
    "    def top(self):\n",
    "        return self.num_list[self.index-1]\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: list[list[int]]) -> list[float]:\n",
    "        num_stack = Stack()\n",
    "\n",
    "        n = len(cars)\n",
    "        meet_time = [0] * n\n",
    "        meet_time[n-1] = -1\n",
    "        num_stack.push(n-1)\n",
    "        speed_error = 0.0000001\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            speed : int = cars[i][1]\n",
    "            pos : int = cars[i][0]\n",
    "\n",
    "            while not num_stack.empty():\n",
    "                top_pos : int = num_stack.top()\n",
    "                cur_meet_time = meet_time[top_pos]\n",
    "                cur_speed : int = cars[top_pos][1]\n",
    "                cur_pos = cars[top_pos][0]\n",
    "\n",
    "\n",
    "                if speed <= cur_speed:\n",
    "                    num_stack.pop()\n",
    "                    continue\n",
    "\n",
    "                tar_meet_time = (cur_pos - pos) / (speed - cur_speed)\n",
    "                meet_time[i] = tar_meet_time\n",
    "\n",
    "                if (cur_meet_time > 0) and (tar_meet_time > cur_meet_time + speed_error):\n",
    "                    num_stack.pop()\n",
    "                    continue\n",
    "\n",
    "                break\n",
    "\n",
    "            if num_stack.empty():\n",
    "                meet_time[i] = -1\n",
    "            num_stack.push(i)\n",
    "\n",
    "        return meet_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n = len(cars)\n",
    "        ans = [-1.0] * n\n",
    "        stack = [] # 单调栈，栈底：车速更慢，且初始位置更靠右\n",
    "\n",
    "        for i in range(n-1, -1, -1): # 从右往左遍历\n",
    "            pos, speed = cars[i]\n",
    "\n",
    "            # 弹出栈顶速度更快的车辆，直到栈顶车的速度小于当前车辆\n",
    "            while stack and speed <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "\n",
    "            # 从栈顶往栈底依次检查当前车是否能及时追上目标车辆\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                time = (cars[j][0] - pos) / (speed - cars[j][1])\n",
    "                if ans[j] < 0 or time <= ans[j]: # 若及时追上了，此即为解\n",
    "                    ans[i] = time\n",
    "                    break \n",
    "                stack.pop() # 否则弹出栈顶这辆已经检查过的车，准备看下一辆\n",
    "\n",
    "            stack.append(i) # 此时当前车辆的速度一定大于栈顶的车辆，需入栈\n",
    "\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "\n",
    "        n = len(cars)\n",
    "        ans = [-1.0] * n\n",
    "        stack = [] # 单调栈，栈底：车速更慢，且初始位置更靠右\n",
    "\n",
    "        for i in range(n-1, -1, -1): # 从右往左遍历\n",
    "            pos, speed = cars[i]\n",
    "\n",
    "            # 弹出栈顶速度更快的车辆，直到栈顶车的速度小于当前车辆\n",
    "            while stack and speed <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "\n",
    "            # 从栈顶往栈底依次检查当前车是否能及时追上目标车辆\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                time = (cars[j][0] - pos) / (speed - cars[j][1])\n",
    "                if ans[j] < 0 or time <= ans[j]: # 若及时追上了，此即为解\n",
    "                    ans[i] = time\n",
    "                    break \n",
    "                stack.pop() # 否则弹出栈顶这辆已经检查过的车，准备看下一辆\n",
    "\n",
    "            stack.append(i) # 此时当前车辆的速度一定大于栈顶的车辆，需入栈\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "\n",
    "        n = len(cars)\n",
    "        res = [-1] * n\n",
    "        stack = [n - 1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            while stack and cars[i][1] <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "            \n",
    "            while stack and (cars[stack[-1]][0] - cars[i][0]) / (cars[i][1] - cars[stack[-1]][1]) > res[stack[-1]] and res[stack[-1]] > 0:\n",
    "                stack.pop()\n",
    "                    \n",
    "            if stack:\n",
    "                res[i] = (cars[stack[-1]][0] - cars[i][0]) / (cars[i][1] - cars[stack[-1]][1])\n",
    "            else:\n",
    "                res[i]\n",
    "            stack.append(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        stack = []\n",
    "        n = len(cars)\n",
    "        res = [0.0] * n\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                if cars[i][1] > cars[j][1]:\n",
    "                    t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])\n",
    "                    if t <= res[j] or res[j] == -1:\n",
    "                        res[i] = t\n",
    "                        break\n",
    "                stack.pop()\n",
    "\n",
    "            if not stack:\n",
    "                res[i] = -1\n",
    "            stack.append(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "#         stack = []\n",
    "#         n = len(cars)\n",
    "#         res = [0.0] * n\n",
    "#         #  每辆车最终追上下一辆车的时间与前边的车没关系，所以倒着计算\n",
    "#         for i in range(n - 1, -1, -1):\n",
    "#             while stack:\n",
    "#                 j = stack[-1]\n",
    "#                 # 如果i车速度大于栈顶车的车速，才有机会追上\n",
    "#                 if cars[i][1] > cars[j][1]:\n",
    "#                     # 如果在当前车 Ci追上右侧第一辆车 Ci+1 之前，Ci+1 已经追上了 Ci+2\n",
    "#                     # 那么，我们就不能用右侧第一辆车 Ci+1 来计算时间了，而应该用 Ci+2\n",
    "#                     # 当然，Ci+2 也有可能先追上 Ci+3\n",
    "#                     t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])\n",
    "#                     if t <= res[j] or res[j] == -1:\n",
    "#                         res[i] = t\n",
    "#                         break\n",
    "#                 stack.pop()\n",
    "\n",
    "#             if not stack:\n",
    "#                 res[i] = -1.0\n",
    "#             stack.append(i)\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        st = []\n",
    "        n = len(cars)\n",
    "        r = [-1] * n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            a,b = cars[i]\n",
    "            while st and b<=cars[st[-1]][1]:\n",
    "                st.pop()\n",
    "            while st:\n",
    "                j = st[-1]\n",
    "                t = (cars[j][0]-a)/(b-cars[j][1])\n",
    "                if r[j] < 0 or t <= r[j]:\n",
    "                    r[i] = t\n",
    "                    break\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        #copy\n",
    "        n = len(cars)\n",
    "        ans = [-1.0] * n\n",
    "        stack  = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            pos,speed  = cars[i]\n",
    "\n",
    "            while stack and speed <= cars[stack[-1]][1]:\n",
    "                stack.pop()\n",
    "            \n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                time = (cars[j][0] -pos)/(speed - cars[j][1])\n",
    "                if ans[j] <0 or time <= ans[j]:\n",
    "                    ans[i] = time\n",
    "                    break\n",
    "                stack.pop()\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        def getCollitionTimeOfTwo(car1, car2):\n",
    "            chaseSpeed = car1[1] - car2[1]\n",
    "            if chaseSpeed <= 0: return -1.0\n",
    "            return (car2[0]-car1[0])/chaseSpeed\n",
    "        n = len(cars)\n",
    "        ret = [-1.0 for _ in range(n)]\n",
    "\n",
    "\n",
    "        stack = []\n",
    "        for carIndex in range(n-1, -1, -1):\n",
    "            car = cars[carIndex]\n",
    "            while stack and cars[stack[-1]][1] >= car[1]:\n",
    "                stack.pop()\n",
    "            while stack:\n",
    "                carToCompare = cars[stack[-1]]\n",
    "                carToCompareCollideT = ret[stack[-1]]\n",
    "                colideTime = getCollitionTimeOfTwo(car, carToCompare)\n",
    "                if carToCompareCollideT < 0 or colideTime <= carToCompareCollideT:\n",
    "                    ret[carIndex] = colideTime\n",
    "                    break\n",
    "                stack.pop()\n",
    "            stack.append(carIndex)\n",
    "                    \n",
    "\n",
    "\n",
    "        return ret\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n = len(cars)\n",
    "        answer = [-1.0] * n\n",
    "        stack = []  # 用于保存尚未找到相遇时间的车辆的索引\n",
    "        \n",
    "        for i in range(n - 1, -1, -1):\n",
    "            pos_i, speed_i = cars[i]\n",
    "            \n",
    "            # 弹出栈中所有不能被第 i 辆车追上的车\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                pos_j, speed_j = cars[j]\n",
    "                \n",
    "                # 如果第 i 辆车的速度小于或等于第 j 辆车，则它永远追不上\n",
    "                if speed_i <= speed_j:\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    # 计算相遇时间\n",
    "                    time = (pos_j - pos_i) / (speed_i - speed_j)\n",
    "                    \n",
    "                    # 如果已知第 j 辆车的相遇时间，并且比计算出的时间要小，则第 i 辆车在此之前会与其他车相遇\n",
    "                    if answer[j] > 0 and time > answer[j]:\n",
    "                        stack.pop()\n",
    "                    else:\n",
    "                        break\n",
    "            \n",
    "            # 计算第 i 辆车的相遇时间（如果可能）\n",
    "            if stack:\n",
    "                j = stack[-1]\n",
    "                pos_j, speed_j = cars[j]\n",
    "                answer[i] = (pos_j - pos_i) / (speed_i - speed_j)\n",
    "            \n",
    "            stack.append(i)\n",
    "        \n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        result, stack, EPS = [-1.0] * (n := len(cars)), deque(), 10 ** -6\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack:\n",
    "                next = stack[-1]\n",
    "                if cars[i][1] > cars[next][1]:\n",
    "                    if (t := 1.0 * (cars[next][0] - cars[i][0]) / (cars[i][1] - cars[next][1])) <= result[next] or abs(result[next] + 1) < EPS:\n",
    "                        result[i] = t\n",
    "                        break\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n = len(cars)\n",
    "        ans = [-1] * n\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p,s = cars[i]\n",
    "            while st and st[-1][2] >= s: st.pop()\n",
    "            while st and ans[st[-1][0]] != -1 and st[-1][1] + ans[st[-1][0]]*st[-1][2] > p + ans[st[-1][0]]*s: st.pop()\n",
    "            if st: ans[i] = (st[-1][1]-p)/(s-st[-1][2])\n",
    "            st.append((i,p,s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        n = len(cars)\n",
    "        res = [-1] * n\n",
    "        stack = [[cars[-1][0], cars[-1][1], 0]]\n",
    "        for i in reversed(range(n-1)):\n",
    "            position_i, speed_i = cars[i]\n",
    "            while stack and stack[-1][1] >= speed_i:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                position, speed, _ = stack[-1]\n",
    "                t = (position - position_i) / (speed_i - speed)\n",
    "                while len(stack) > 1 and t >= stack[-2][2]:\n",
    "                    stack.pop()\n",
    "                    position, speed, _ = stack[-1]\n",
    "                    t = (position - position_i) / (speed_i - speed)\n",
    "                stack[-1][2] = t\n",
    "                res[i] = t\n",
    "            stack.append([position_i, speed_i, 0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getCollisionTimes(self, cars: List[List[int]]) -> List[float]:\n",
    "        stark, res = [], []\n",
    "        for y, k in reversed(cars):\n",
    "            while len(stark) > 1 and stark[-1][0] * k + y <= stark[-1][1]:\n",
    "                stark.pop()\n",
    "            if stark and stark[-1][2] < k:\n",
    "                a, b, c = stark[-1]\n",
    "                X = b-a*c\n",
    "                res.append((X-y)/(k-c))\n",
    "                stark.append([(X-y)/(k-c), (k*X-y*c)/(k-c), k])\n",
    "            else:\n",
    "                res.append(-1.0)\n",
    "                stark = [[0,y,k]]\n",
    "        return res[::-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
